package com.TheEndWork;

import java.util.ArrayDeque;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/**
 * @authoer zsj
 * @date 2022/5/27 17:13
 * <p>
 * 因为十分重要
 * 用中文命名来标志
 */
public class 经典算法之深度和广度优先搜索 {

    /**
     * 有 n 个城市，其中一些彼此相连，另一些没有相连。
     * 如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。
     * 省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。
     * 给你一个 n x n 的矩阵 isConnected ，
     * 其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。
     * 返回矩阵中 省份 的数量。
     */
    public int findCircleNum(int[][] isConnected) {
        int citys = isConnected.length;
        //相当于是一个省份包含多个城市
        boolean[] visited = new boolean[citys];//被访问过的记录
        int ans = 0;
        //如果当前节点是被记录的并且不=0的话，就回溯
        for (int i = 0; i < citys; i++) {
            //因为创建数组的时候，默认是false，所以我们要取反
            if (!visited[i]) {
                //开始递归遍历，将所有与当前城市直接相连或者间接相连的记录为true
                //dfs所需参数(),关键在如何回溯
                dfs(i, citys, visited, isConnected);
                ans++;
            }
        }
        return ans;
    }

    /**
     * 深度优先遍历
     *
     * @param i           遍历开始长度
     * @param citys       城市数量
     * @param visited     标记数组
     * @param isConnected 初始二维数组
     */
    private void dfs(int i, int citys, boolean[] visited, int[][] isConnected) {
        for (int index = 0; index < citys; index++) {
            //需要判断一下二维数组中的数字是不是1并且还要没有被标记过
            if (isConnected[i][index] == 1 && !visited[index]) {
                //说明属于这个省份，标记即可
                visited[index] = true;
                //继续往下遍历
                dfs(index, citys, visited, isConnected);
            }
        }
    }

    /**
     * 给你一个大小为 m x n 的二进制矩阵 grid 。
     * 岛屿是由一些相邻的1(代表土地) 构成的组合，
     * 这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。
     * 你可以假设grid 的四个边缘都被 0（代表水）包围着。
     * 岛屿的面积是岛上值为 1 的单元格的数目。
     * 计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。
     */
    public static int maxAreaOfIsland(int[][] grid) {
        //思路  我们需要深度去找出所有的岛屿，并且记录岛屿的面积
        int max = 0;
        int n = grid[0].length;
        int m = grid.length;
        boolean[][] visited = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1 && !visited[i][j]) {
                    max = Math.max(dfs(grid, i, j, visited), max);
                }
            }
        }
        return max;
    }

    /**
     * 深度搜索出当前岛屿的面积
     */
    public static int dfs(int[][] grid, int i, int j, boolean[][] visited) {
        //设置递归结束条件
        if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || visited[i][j] || grid[i][j] == 0) {
            return 0;
        }
        int ans = 1;
        //没有被访问过
        visited[i][j] = true;
        ans += dfs(grid, i + 1, j, visited);
        ans += dfs(grid, i - 1, j, visited);
        ans += dfs(grid, i, j + 1, visited);
        ans += dfs(grid, i, j - 1, visited);

        return ans;
    }


    /**
     * 你有一张某海域 NxNNxN 像素的照片，"."表示海洋、"#"表示陆地，如下所示：
     * <p>
     * .......
     * <p>
     * .##....
     * <p>
     * .##....
     * <p>
     * ....##.
     * <p>
     * ..####.
     * <p>
     * ...###.
     * <p>
     * .......
     * <p>
     * 其中"上下左右"四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有 2 座岛屿。
     * <p>
     * 由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)，它就会被淹没。
     * <p>
     * 例如上图中的海域未来会变成如下样子：
     * <p>
     * .......
     * <p>
     * .......
     * <p>
     * .......
     * <p>
     * .......
     * <p>
     * ....#..
     * <p>
     * .......
     * <p>
     * .......
     * 请你计算：依照科学家的预测，照片中有多少岛屿会被完全淹没。
     */
    public static void lanqiao178() {
        Scanner scan = new Scanner(System.in);
        int length = scan.nextInt();
        String[][] island = new String[length][length];
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < island.length; j++) {
                island[i][j] = scan.next();
            }
        }
        int ans = 0;
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < island.length; j++) {
                if (island[i][j].equals("#")) {
                    //说明当前的是岛,寻找他的四周看有没有海洋
                    if (!isDown(island, i, j)) {
                        ans += 1;
                    }
                }
            }
        }
        System.out.println(ans);
        scan.close();
    }

    /**
     * 判断当前岛屿会不会
     *
     * @param island
     * @param i
     * @param j
     */
    private static boolean isDown(String[][] island, int i, int j) {
        if (!island[i + 1][j].isEmpty()) {
            if (island[i + 1][j].equals(".")) {
                return true;
            }
        }
        if (!island[i - 1][j].isEmpty()) {
            if (island[i - 1][j].equals(".")) {
                return true;
            }
        }
        if (!island[i][j + 1].isEmpty()) {
            if (island[i][j + 1].equals(".")) {
                return true;
            }
        }
        if (!island[i][j - 1].isEmpty()) {
            if (island[i][j - 1].equals(".")) {
                return true;
            }
        }
        return false;
    }


    public static void main(String[] args) {
//        int[][] n = {{0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
//                {0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0}
//                , {0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0},
//                {0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0},
//                {0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0},
//                {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0},
//                {0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0},
//                {0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0}};
        char[][] n = {{'1', '1', '1', '1', '0'}, {'1', '1', '0', '1', '0'}, {'1', '1', '0', '0', '0'},
                {'0', '0', '0', '0', '0'}};

        numIslands(n);
    }

    /**
     * 给你一个由'1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
     * 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
     * 此外，你可以假设该网格的四条边均被水包围。
     */
    public static int numIslands(char[][] grid) {
        int n = grid.length, ans = 0, m = grid[0].length;
        boolean[][] visited = new boolean[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == '1' && !visited[i][j]) {
                    ans += dfs2(grid, visited, i, j);
                }
            }
        }
        return ans;
    }

    private static int dfs2(char[][] grid, boolean[][] visited, int i, int j) {
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || visited[i][j] || grid[i][j] == '0') {
            return 0;
        }
        visited[i][j] = true;
        dfs2(grid, visited, i + 1, j);
        dfs2(grid, visited, i - 1, j);
        dfs2(grid, visited, i, j + 1);
        dfs2(grid, visited, i, j - 1);
        return 1;
    }


    /**
     * 广度优先搜索  BFS
     * 类似分层搜索的过程          1
     * 1          1 1 1
     * 1 ->   1 1 1  ->  1 1 1 1 1
     * 1          1 1 1
     * 1
     */
    public void bfs() {

    }
}
